package study.算法Algorithm.常用10种算法.二分查找;

import java.util.ArrayList;
import java.util.List;

/*
    二分查找-非递归
 */
public class BinarySearch {

    public static void main(String[] args) {
        //测试
        int[] arr = {1, 3, 8, 10, 11, 11, 11, 67, 100};
        List list = binarySearch(arr, 11);
        System.out.println("list = " + list);
    }

    //二分查找的非递归实现

    /**
     * @param arr    待查找的数组  arr是升序数组
     * @param target 查找的数，  查找的数在数组中可能存在多个
     * @return 返回对应下标的集合   null表示没找到
     */
    public static List binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                List<Integer> list = new ArrayList<>();
                int temp = mid - 1;
                while (true) {
                    if (temp < 0 || arr[temp] != target) {
                        break;
                    } else {
                        list.add(temp);
                        temp--;
                    }
                }
                list.add(mid);
                temp = mid + 1;
                while (true) {
                    if (temp > right || arr[temp] != target) {
                        break;
                    } else {
                        list.add(temp);
                        temp++;
                    }
                }
                return list;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else if (arr[mid] > target) {
                right = mid - 1;
            }
        }
        return null;
    }
}
